One-Staged Wormhole Routing for Irregular Faulty Patterns in Meshes”, submitted to The tenth international conference on parallel and distributed systems (ICPADS

A fault-tolerant wormhole routing algorithm in mesh multicomputer is proposed, which enables two good nodes to exchange their messages, except that there is no routing path between them, in one stage without aid of global infor-mation. In the method, faulty nodes are enclosed with faulty blocks. And, a message is routed to reach the destination or go out of the faulty block via multiple pre-established inter-mediate nodes if it is on the inside of a faulty block. A mes-sage not on the inside of a faulty block is routed toward the destination till it encounters the faulty block enclosing the destination, and is then routed toward the intermediate node which is able to instruct it to go into the faulty block. Rout-ing algorithm RFB which permits the change of the rout-ing direction is designed for the message not on the inside of a faulty block, which makes it possible that the message reaches the intermediate node in one stage. In our method, each channel is required to be split into two virtual ones